- Entstehung
- Standard PSO
- Beispiel 2D
- Nebenbedingungen
- Beispiel 2D mit Nebenbedingungen
- Konvergenz
- Vor- und Nachteile
- Fazit
2022-11-07
Optimierungsproblem:
Vehalten des PSO:
Initialisiere zufällige Positionen \(x^{k, i}\) und Richtungsvektoren \(v^{k, i}\) der Partikel \(k\) in Iteration \(i=0\)
Evaluiere die Kostenfunktion mit der Position jedes Partikels
Speicher die bisher beste Position pro Partikel in \(p_{best}^{k,i}\)
Speicher die bisher beste Position aller Partikel in \(g_{best}^i\)
Iterationsschritt \(i \rightarrow i+1\) pro Partikel \(k\): \[ \begin{aligned} v^{k, i+1} &= w \cdot v^{k, i} + c_p \cdot r_1^{k,i} \cdot (p_{best}^{k,i}-x^{k,i}) + c_g \cdot r_2^{k,i} \cdot (g_{best}^{k,i}-x^{k,i}) \\ x^{k, i+1} &= x^{k, i} + v^{k, i+1} \end{aligned} \]
Wiederhole Schritt 2-5 bis die Abbruchbedingung erreicht ist
Zielfunktion:
\[
\begin{aligned}
f(x, y) =& -20\cdot e^{-0.2 \cdot \sqrt{0.5 \cdot ((x-1)^2 + (y-1)^2)}} \\
& \ - e^{0.5 \cdot ( cos(2\cdot \pi \cdot x) + cos(2\cdot \pi \cdot y))} + e + 20
\end{aligned}
\] Aufgabe:
Minimiere \(f(x,y)\) mit \(-10 \leq x \leq 10\) und \(-10 \leq y \leq 10\)
Beispiele:
Methoden:
Alte Zielfunktion: \(f(x)\) mit \(f: \mathbb{R}^n \rightarrow \mathbb{R}\)
Bruch von Nebenbedingungen: \(g(x)\) mit \(g(x) \geq 0 \ \forall x \in \mathbb{R}^n\)
Neue Zielfunktion: \(z(x) = f(x) + g(x)\)
Beispiel für gängige Nebenbedingungen: \[ A^T \times x \geq b_0 \] Dann könnte \(g(x)\) wie folgt aussehen: \[ g(x) = ||\vec{\lambda}( A^T \times x - b_0 )||_2^2 \] mit elementweiser Anwendung von \[ \lambda(x) = \begin{cases} 0 &\text{ if }x \geq 0\\ x &\text{ if }x < 0 \end{cases} \]
Gomez and Levy function (modified)
Convergence Analysis for Particle Swarm Optimization (von Berthold Schmitt)
Einschränkung: \(p_{best}\) und \(g_{best}\) sind konstant
Folgerung: Partikel sind unabhängig
\[ \begin{aligned} v^{i+1} &= w \cdot v^{i} + c_p \cdot r_1^{i} \cdot (p_{best}^{i}-x^{i}) + c_g \cdot r_2^{i} \cdot (g_{best}^{i}-x^{i}) \\ x^{i+1} &= x^{i} + v^{i+1} \end{aligned} \] Theorem 1: Gegeben \(w\), \(c_p\), \(c_g \geq 0\) und es gilt \(0 \leq w <1\) und \(0 < c_p + c_g < 4\cdot(1+w)\) dann konvergiert der iterative Prozess \(E(x^i)_{i \in \mathbb{N}}\) fast sicher gegen \[ \mu := \frac{c_p \cdot p_{best} + c_g \cdot g_{best}}{c_p +c_g} \]
Theorem 2: Gegeben \(w\), \(c_p\), \(c_g \geq 0\) und es gilt \(0 \leq w <1\), \(c_p + c_g > 0\) und \(g>0\) mit \[ g := 1-((1+w-\frac{c_p+c_g}{2})^2+\frac{1}{12}\cdot (c_p^2+c_g^2)-w)\cdot (1-w)-w^3 \] dann konvergiert der iterative Prozess \(Var(x^i)_{i \in \mathbb{N}}\) fast sicher gegen \[ \sigma^2 := \frac{1}{6} \cdot (\frac{c_p \cdot c_g}{c_p + c_g})^2\cdot (g_{best}-p_{best})^2\cdot (1-w) / g \]\(f=\) 0.9033333
Nachteile:
Vorteile: